What is quadratic probing?

Quadratic probing is a technique used in hash tables to resolve collisions that may occur when two keys hash to the same index. When a collision occurs, instead of placing the new key-value pair in the next available slot, quadratic probing calculates a new position by incrementing the current position by a quadratic function.

The new position is calculated using the formula: (hash(key) + c1 * i + c2 * i^2) % table_size, where hash(key) is the original index of the key, c1 and c2 are constants, i is the iteration count, and table_size is the size of the hash table.

Quadratic probing is preferred over linear probing because it helps to reduce clustering, a phenomenon where keys tend to cluster together in the hash table. However, quadratic probing can still suffer from clustering as it may not always find an empty slot after a collision.

Overall, quadratic probing is a simple and efficient collision resolution technique that is commonly used in hash tables to handle collisions.